The present invention relates generally to cryptographic methods and systems to be used in digital data processing, and in particular, is directed to cryptographic methods and systems using block ciphers employing balanced Feistel networks with hash functions as round functions.
There are two categories of symmetric key-based cryptographic algorithms. Stream ciphers convert plaintext to ciphertext one bit (or byte) at a time. Block ciphers operate on groups of bits called "blocks." A block cipher that mixes layers of substitution and permutation is called a Substitution-Permutation Network (SPN). SPNs are alternating layers of nonlinear substitution boxes (s-boxes) and linear permutations which serve to scramble the bits of the plaintext in a key-dependent way to create the ciphertext. An s-box layer and a permutation layer together are often referred to as a single "round."
The input to the cipher is a block of plaintext 2n bits in length. There are two general classes of SPNs: those that operate on the full 2n bits of data in each round; and those that operate on fewer than 2n bits (i.e., partial blocks) and then swap the partial blocks between rounds. The second class is what is typically meant in the cryptographic literature by the terms "Feistel cipher" and "Feistel network." The DES (U.S. Data Encryption Standard) was constructed using this approach.
The general structure of an r-round Feistel network is shown in FIG. 1a. Basic encryption operation is as follows. A plaintext message block 105 of 2n bits is input and split into a left half L.sub.0 110 and a right half R.sub.0 115. If the message block is divided into two equal blocks of length n, the Feistel network is said to be "balanced." Right half R.sub.0 115, and key K.sub.0 120 are input to round function f.sub.0 125, the output of which is used to modify left half L.sub.0 110. In FIG. 1a, L.sub.0 110 is modified using XOR addition at 114. The result becomes R.sub.1 and is used as the next input to function f.sub.1 at 130; R.sub.0 115 then becomes L.sub.1. Swapping the left and right halves completes round one. This process continues for as many rounds as the cipher requires. After the final round, which does not contain a swap in order to simplify implementation of the decryption process, the left and right halves are concatenated to form ciphertext 140.
In symmetric cryptographic algorithms based on Feistel networks, the same process works for both encryption and decryption with minimal modifications. The decryption process is essentially the encryption process in reverse order. Referring again to FIG. 1a, in the decryption process, ciphertext message block 140 of 2n bits would be split into a left half L.sub.r 145 and a right half R.sub.r 150. Right half R.sub.r 150, and key K.sub.r-1 165 are input to round function f.sub.r-1 155, the output of which is used to modify left half L.sub.r 170. L.sub.r 145 is modified using XOR addition at 160. The result becomes R.sub.r-1 and is used as the next input to function f.sub.r-2 ; R.sub.r then becomes L.sub.r-1. Swapping the left and right halves completes round one. To complete the decryption process, the final left and right halves are concatenated to form plaintext 105.
The security of block ciphers based on Feistel networks is directly related to the ability of the round function to resist cryptanalytic attack. In their 1988 paper, "How to Construct Pseudorandom Permutations From Pseudorandom Functions," SIAM Journal of Computing, Vol. 17, No. 2 (April 1988), M. Luby and C. Rackoff showed that provably secure three- or four-round Feistel networks can be constructed using secure pseudorandom functions as the component round functions. They were able to show that three-round networks provide security against chosen plaintext attacks provided that no more than k plaintext blocks are encrypted and assuming the adversary does not have unlimited computing power with which to perform exhaustive key search for keys of reasonable length. Furthermore, four-round Feistel networks, sometimes called super pseudorandom invertible permutations, are secure against chosen ciphertext attacks under the same conditions. Such attacks are among the strongest known against any cryptosystem, so efficient ciphers which are secure against these attacks would be of immediate value in a number of environments.
Some researchers have replaced secure, but inefficient, pseudorandom functions with known hash functions such as MD5, SHA-1, or RIPE-MD. While these ciphers are faster to execute, they are no longer provably secure, since no hash function has yet been proven to be a pseudorandom function. These ciphers also tend to be "unbalanced" Feistel networks (in which the plaintext is split into two pieces of size) and may incorporate other primitive techniques, such as a steam cipher, to deal with the unbalance. This can complicate the analysis of such ciphers so that it is even more difficult to gain confidence in their security.
Using a smaller Luby-Rackoff cipher as the round function in a recursive design also has been suggested. For example, a 4n bit to 4n bit Luby-Rackoff cipher uses 2n-bit to 2n-bit Luby-Rackoff ciphers as its round functions, each of which uses n-bit to n-bit Luby Rackoff ciphers for its round functions, and so on. Researchers have shown, however, that a cipher of this design can be used to encrypt only a handful of plaintexts before security is threatened. See U. Maurer, "A Simplified and Generalized Treatment of Luby-Rackoff Pseudorandom Permutation Generators," in Advances in Cryptography: Proceedings of Eurocrypt 92, Springer (1993), pp. 189-203.
Furthermore, research has shown that the theoretical security of any block cipher is at most the square root of the size of the keyspace (due to so-called key-collision attacks), so that for true 128-bit security, 256-bit keys must be used. See E. Biham, "How to Forge DES-Encrypted Messages in 2.sup.28 steps," Technical Report CS 884, Dept. of Computer Science, Technion, Haifa, Israel, August 1996. Ciphers with large block sizes may be used with a large number of plaintexts (up to the square root of the block size), so that ciphers with larger block sizes may be appropriate even for environments in which many terabytes of data must be encrypted with a single key.
It is therefore desirable to develop a cipher that has the simplicity of the balanced Feistel network plus the efficiency of hash functions.
It is also desirable to construct Feistel network-based ciphers that rest on the theoretical underpinnings of Luby and Rackoff.
It is further desirable to create a function which retains the apparent pseudorandom properties of MD5 and SHA-1, but which is more suitable for a fixed-size, symmetric block cipher.
It is also desirable to develop a cipher that even with large key sizes is computationally fast to implement.
Additionally, it is desirable that the key scheduling process not be prohibitively long compared with, for example, the encryption or decryption of a single block of plaintext.